package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 单向选择排序
 * 算法思想：
 *          第一趟，从n个记录中找出关键字最小的记录与第一个记录交换；
 *          第二趟，从n-1个记录中找出关键字最小的记录与第二个记录交换
 *          ·····
 * 选择排序与冒泡排序之间的比较：
 *          并且选择排序关键字的比较次数是1/2n*(n-1)
 *          耗费时间：2.91s
 */
public class SelectSorting {
    public static void main(String[] args) {
        int []arrays = {3,9,-1,20,10};
        select(arrays);
        System.out.println(Arrays.toString(arrays));
        //costTime();
    }

    /**
     * 从低到高进行排序，最外层低排序只需要length-1次。
     *
     * @param array
     */
    public static void select(int []array){
        int length = array.length;
        for (int i = 0; i <length-1; i++) {
            int min = array[i];
            int minIndex = i;
            for (int j = i; j <= length-1; j++) {
                if (min>array[j]) {
                    min = array[j];
                    minIndex = j;
                }
            }
            // 交换最小值,如果有交换index有变化 -->
                array[minIndex] = array[i];
                array[i] = min;
        }
    }
    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays3 = new int[80000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(80000);
        }
        long startTime = System.currentTimeMillis();
        select(arrays3);   // 正规的插入，有值的后移
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}
